package oj;

import java.util.LinkedList;
import java.util.Queue;

public class Num662 {
    public int widthOfBinaryTree(TreeNode root) {
        if(root==null){
            return 0;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        LinkedList<Integer> index=new LinkedList<>();
        queue.offer(root);
        index.addLast(root.val);
        int maxWidth=1;
        while (!queue.isEmpty()){
            int size=queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode tmp=queue.poll();
                int cur=index.removeFirst();
                if(tmp.left!=null){
                    queue.offer(tmp.left);
                    index.addLast(cur*2+1);
                }
                if ((tmp.right!=null)){
                    queue.offer(tmp.right);
                    index.addLast(cur*2+2);
                }
            }
            //每遍历完一层，就计算该层宽度
            if(index.size()>1){
                maxWidth=Math.max(maxWidth, index.peekLast())- index.peekFirst()+1;
            }
        }
        return maxWidth;
    }
}
